\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

% \title{堆排序和快速排序的比较和测试}


% \author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}
               胡宇梦      3210103435
% \maketitle

\section{设计思路}
图可以被表示为 G={V, E}，其中 V={v1, ... , vN}，E= {e1, ... , eM}。（也就是说，V是节点的集合，即所谓的点集，E是连接两点的线即两点间关系的集合，即所谓的边集。
 在顶点集合所包含的若干个顶点之间，可能存在着某种两两关系——如果某两个点之间的确存在这样的关系的话，我们就在这两个点之间连边，这样就得到了边集的一个成员。

所以图的基本组成是：点集和边集。


但是，图的每一条边上可能会带有相应的值，这就是权重，根据有无权重，图可分为有权图和无权图；根据边有无方向，图又可以分为无向图和有向图；而且如何储存图，又有多种方法，比如邻接矩阵和邻接表。
所以，本文的设计思路为：定义一个基本图类Graph，成员变量有
Weight（是否有权重），Directed（是否有向），点集（numVertexes）,和边
集（numEdges）;


本项目实现了三个类，Graph类上文已说明，邻接矩阵图类（MatrixGraph）和邻接表图类（AdjlistGraph）
均继承于基本图类Graph。三个类的基本成员以及成员函数如下图所示。

\begin{figure}[ht]
    \centering
    \includegraphics[width=8.5cm]{1.png}
    \caption{UML类图}
    \label{mode=1}
\end{figure}  

\section{程序验证}

生成图的流程为：指定存储方式后，从txt文本文件中读取图的
点集和边集信息生成
图。测试代码以及测试流程如代码以及注释所示：
\begin{figure}[ht]
    \centering
    \includegraphics[width=5cm]{3.png}
    \caption{测试代码}
    \label{mode=1}
\end{figure}  

2.1 存储方式选择测试。通过输入flag确定存储方式，输入1即使用
邻接矩阵，输入2使用邻接表，输入其他，程序报错。测试结果如下图所示：
\begin{figure}[ht]
    \centering
    \includegraphics[width=5cm]{4.png}
    \caption{存储方式选择测试结果}
    \label{mode=1}
\end{figure} 

2.2 listVertexes点和listEdges函数测试。左图使用邻接矩阵，列出了点和边；
右图使用邻接表，列出了点和边，测试成功。

\begin{figure}[ht]
    \centering
    \includegraphics[width=13.3cm]{7.png}
    \label{mode=1}
\end{figure}  

\end{document}
